// -100 < x < 100
// -2**31 <= n <= 2**31 - 1
// -10**4 <= x**n <= 10 ** 4  <=> -10 << 2 <= x << (n / 2) <= 10 << 2

// 2 ** 6  2 << Math.sqrt(6)
// 2 ** 4  2 << 2
// O(N)
function pow(x, n) {
  let res = 1
  while (n > 0) {
    res *= x
    n -= 1
  }
  return res
}

console.log(pow(2, 10))

// 实现 Math.pow()
// 使用二分法
// O(logN)
function power(a, n) {
  if (n < 0) {
    if (a === 0) return Infinity
    return 1 / power(a, -n)
  }
  if (n === 0) return 1

  let r = power(a, n / 2)

  // return n % 2 === 1 ? r * r * a : r * r
  return n & 1 ? r * r * a : r * r
}
// O(logN) 位运算 + loop 没有栈溢出的风险，二进制操作更快
var myPow = function (a, n) {
  if (n < 0) {
    a = 1 / a
    n = -n
  }
  let res = 1
  while (n) {
    if (n & 1) {
      res *= a
    }
    n >>= 1
    a *= a
  }
  return res
}
